1782C - Equal Frequencies - CodeForces Solution

#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>

void solve() {
    int n = 0;
    std::string str;
    std::cin >> n >> str;

    std::vector<std::pair<int, char>> map;
    for (char chr = 'a'; chr <= 'z'; ++chr) {
        map.push_back({0, chr});
    }
    for (int i = 0; i < n; ++i) {
        ++map[str[i] - 'a'].first;
    }
    std::sort(map.rbegin(), map.rend());

    int answer = -1;
    int letter_count = -1;
    for (int l_cnt = 1; l_cnt <= 26; ++l_cnt) {
        if (n % l_cnt)
            continue;
        int freq = n / l_cnt;
        int new_answer = 0;
        for (int i = 0; i < l_cnt; ++i) {
            if (map[i].first < freq)
                new_answer += freq - map[i].first;
        }

        if (answer == -1 || new_answer < answer) {
            answer = new_answer;
            letter_count = l_cnt;
        }
    }
    std::cout << answer << "\n";
    int freq = n / letter_count;

    std::map<char, int> fixed;
    std::queue<char> q;
    for (int i = 0; i < letter_count; ++i) {
        fixed[map[i].second] = map[i].first;
        if (map[i].first < freq) {
            for (int j = 0; j < freq - map[i].first; ++j) {
                q.push(map[i].second);
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        if (!fixed.count(str[i]) || fixed[str[i]] > freq) {
            if (fixed.count(str[i]))
                --fixed[str[i]];
            str[i] = q.front();
            q.pop();
        }
    }

    std::cout << str << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

#ifndef ONLINE_JUDGE
    std::freopen("input.txt", "r", stdin);
#endif

    int tests = 0;
    std::cin >> tests;
    while (tests--)
        solve();

    return 0;
}